public class Node{
    public int value;
    public Node left;
    public Node right;
    public Node(int data){
        this.value=data;
    }
}

//recursion 前序：根 左 右

public void preOrder(Node head){
    if(head==null){
        return;
    }

    system.out.print(head.value+" ");
    preOrder(head.left);
    preOrder(head.right);
}

//use one stack

public void preOrder(Node head){
  if(head!=null){

    Stack<Node> s1=new Stack<>();
    s1.push(head);
    if(!s1.isEmpty()){
        head=s1.pop();
        System.out.print(head.value+" ");
        if(head.left!=null){
            s1.push(head.left);
        }
        if(head.right!=null){
            s1.push(head.right);
        }
    }
  }
  
    System.out.println();
}